package 算法.leetcode.bytedance;

import java.util.HashMap;
import java.util.Map;

/**
 * @author lchenglong
 * @date 2022/5/9
 */
public class OfferArray_VI {

    public static void main(String[] args) {
        int[][] isConnected = new int[][]{{1,1,0},{1,1,0},{0,0,1}};
        OfferArray_VI instance = new OfferArray_VI();
        int ans = instance.findCircleNum(isConnected);
        System.out.println(ans);
    }
    public int findCircleNum(int[][] isConnected) {
        UnionFind uf = new UnionFind();
        for (int i=0;i<isConnected.length;i++){
            uf.add(i);
            for (int j=0;j<i;j++ ){
                if (isConnected[i][j] == 1){
                    uf.merge(i,j);
                }
            }
        }
        return uf.getNumOfSets();
    }

    class UnionFind {
        // 记录父节点
        Map<Integer,Integer> father;
        private Integer numOfSets;
        // 构造方法
        public UnionFind(){
            father  = new HashMap<>();
            numOfSets = 0;
        }

        public void add(int x){
            if (!father.containsKey(x)){
                // 初始节点
                father.put(x,null);
                numOfSets++;
            }
        }

        public void merge(int x,int y){
            int rootX = find(x);
            int rootY = find(y);
            // 不相连
            if (rootX!=rootY){
                // 先使之相连
                father.put(rootX,rootY);
                // 不相连的设置为相连了,需要把相连的数减一
                numOfSets--;
            }
        }

        public int find(int x){
            int root = x;
            // 找其祖先
            while (father.get(root)!=null){
                root = father.get(root);
            }

            // 路径压缩, 存储叶子到根的连通关系
            while (x!=root){
                int origin_father = father.get(x);
                father.put(x,root);
                x = origin_father;
            }
            return root;
        }

        // 有共同祖先说明是相连的
        public boolean isConnected(int x,int y){
            return find(x) == find(y);
        }

        public int getNumOfSets() {
            return numOfSets;
        }

    }


}
